package com.atfcm.link;

/**
 * @Author whaty
 * @create 2024/11/11 16:43
 */
public class T234回文链表 {
    // 1 2 3  3 2   1
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null) {
//            if(fast.next ==null){
//                //奇数
//            }else if(fast.next.next == null){
//                //偶数个
//            }
            fast = fast.next == null ? null : fast.next.next;

            if (fast != null) {
                slow = slow.next;
            }
        }

        ListNode newHead = slow.next;
        slow.next = null;

        newHead = reverseList(newHead);

        while (newHead != null && head != null) {
            if (head.val != newHead.val) {
                return false;
            }
            newHead = newHead.next;
            head = head.next;
        }
        return true;


    }

    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode reverse = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return reverse;
    }

      static   class ListNode {
        public int val;
        public ListNode next;

        ListNode(int val) {
            this.val = val;
        }
    }
}
